/**
 * 700. 二叉搜索树中的搜索
 * https://leetcode-cn.com/problems/search-in-a-binary-search-tree/
 */
public class Solutions_700 {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(4);
        root.left = new TreeNode(2);
        root.left.left = new TreeNode(1);
        root.left.right = new TreeNode(3);
        root.right = new TreeNode(7);
        int val = 2;  // output: {2, 1, 3}
//        int val = 5;  // output: null;

        TreeNode result = searchBST(root, val);
        System.out.println(result);
    }

    /**
     * 递归方式实现
     * 根据二叉搜索树特性：左子树中的元素一定小于根节点值，右子树中的元素一定大于根节点值
     */
    public static TreeNode searchBST2(TreeNode root, int val) {
        if (root == null) {
            return null;
        }
        if (root.val == val) {
            return root;
        } else if (root.val > val) {
            // 根节点值大于 val，递归进入左子树，左子树中的节点值一定小于根节点值，那么可能存在 val
            return searchBST(root.left, val);
        } else {
            // 根节点值小于 val，递归进入右子树，右子树中的节点值一定大于根节点值，那么可能存在 val
            return searchBST(root.right, val);
        }
    }

    /**
     * 迭代方式实现（模拟递归）
     * 根据二叉搜索树特性：左子树中的元素一定小于根节点值，右子树中的元素一定大于根节点值
     */
    public static TreeNode searchBST(TreeNode root, int val) {
        while (root != null) {
            if (root.val == val) {
                return root;
            }
            root = root.val > val ? root.left : root.right;
        }
        return null;
    }
}
